package com.jhy.review.paixu;

/**
 * @author go_jhy
 * @create 2022/6/10 - 下午 10:10
 * 小和问题 是归并排序的应用
 * 1 3 4 2 5
 * 1的左边比它小的数 没有（0）
 * 3的左边比他小的数 为 1（1） 4：（4） 2（1） 5（10） 一共为16
 * 在merge当中 就可以求出所有的数的小和
 * <p>
 * 等同于在一个数当中 右边的数几个比它大 1的话就是4个1  3的话就是 2个3...  加起来也是16（用归并排序求）
 * <p>
 * <p>
 * 1 3 4 2 5
 * 134  左侧  13 左侧   4 是右侧   13来说  1左侧  3 右侧
 * 25   右侧
 * <p>
 * <p>
 * 一定要排序  在计算当中的时候一定要排序  因为这样才能算出 右边有几个数比左边大 就可以直接用下标算了
 * 不会漏算 不会重算 在排序之前就已经计算了小和了
 */

@SuppressWarnings("all")
public class Code02_SmallSum {

    //求小和的总函数
    public static int smallSum(int[] arr) {
        if (arr == null && arr.length < 2) {
            return 0;
        }
        return mergeSort(arr, 0, arr.length - 1);
    }


    //递归 先给数组分层两个部分，每一个部分都是有序的
    public static int mergeSort(int[] arr, int l, int r) {
        //终止条件
        if (l == r) {
            return 0;
        }
        int mid = l + ((r - l) >> 1);
        //左边的小和
        return mergeSort(arr, l, mid) +
                //右边的小和
                mergeSort(arr, mid + 1, r) +
                //总的小和
                merge(arr, l, mid, r);

    }


    //排序并求小和
    public static int merge(int[] arr, int l, int m, int r) {
        //声明一个辅助的空间,数组长度一个
        int[] help = new int[r - l + 1];
        int i = 0;
        int p1 = l;
        int p2 = m + 1;
        int res = 0;
        while (p1 <= m && p2 <= r) {
            //记录右边有几个数比本身这个数大 然后乘以这个数
            res += arr[p1] < arr[p2] ? (r - p2 + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        //然后将辅助的这个数组 复制到原来的数组当中去
        for (int j = 0; j < help.length; j++) {
            arr[j + l] = help[j++];
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {5,4,2,6,8,1};
        int i = smallSum(arr);
        System.out.println(i);
    }


}
